package homework;

public class homework10 {
    public static void main(String[] args) {
    /*
     描述：希尔排序就是先定义一个增量，然后根据这个增量将几个元素分成一组，
     最终可能会得到很多个组，在组内进行插入排序，每个组都完成排序后再缩小增量，
     再排序，直到增量为1，也就是所有排序都成为了一组，这个时候就变成了最简单的插入排序了。
     */

    }
    public static void sort(int[] arr, int gap) {
        //确定新一轮分组的增量
        gap = gap / 2;
        //对数组进行分组
        for (int i = 0; i < gap; i++) {
            for (int j = i + gap; j < arr.length; j += gap) {
                //获取当前元素，然后在本组内部向前比较并排序
                int current = arr[j];
                for (int k = j - gap; k >= i; k -= gap) {
                    if (arr[k] > current) {
                        //插入
                        arr[k + gap] = arr[k];
                        arr[k] = current;
                    }
                }
            }
        }

        if (gap > 1) {
            sort(arr, gap);
        }
    }

}
